Apprentissage par différences temporelles (Temporal-Difference - TD)

6. Méthode Q-Learning : Contrôle de type Off-Policy

Nous allons maintenant nous intéresser à l'utilisation des méthodes par différences temporelles dans le but de construire des stratégies optimales. Comme d'habitude, nous allons suivre les idées proposées par les méthodes d'itérations des stratégies généralisées (GPI), en utilisant les méthodes TD pour l'évaluation et la prédiction. Comme pour les méthodes de Monte-Carlo nous allons être confronté au problème de balance entre l'exploitation et l'exploration. Ici nous nous intéressons à une méthode de type Off-Policy.

6.1. Présentation de la méthode Q-Learning

Cette méthode est définie par l'équation suivante:

$$Q\left( {{S_t},{A_t}} \right) \leftarrow Q\left( {{S_t},{A_t}} \right) + \alpha \left[ {{R_{t + 1}} + \gamma \mathop {\max }\limits_a Q\left( {{S_{t + 1}},a} \right) - Q\left( {{S_t},{A_t}} \right)} \right]$$

Dans ce cas, la fonction des valeurs d'actions apprise $Q$ approxime directement la valeur optimale $Q^*$, et cela indépendemment de la stratégie suivie. Cela simplifie considérablement l'algorithme. La stratégie a toujours un effet sur l'apprentissage du fait qu'elle détermine quelles sont les paires d'état-action visitées et mises à jour. Cependant, tout ce qui est nécessaire pour que l'algorithme converge est que ces paires soient mises à jour de manière continue. On montre que sous ces conditions, $Q$ converge avec une probabilité de 1 vers $Q^*$.

De manière schématisé, les deux diagrammes ci-dessous permettent de représenter le fonctionner des deux algorithmes Sarsa et Q-Learning:

Algorithme

Pourquoi la méthode Q-learning est-elle de type Off-Policy ?

Même si cela n'est pas visible au premier coup d'oeil, cette méthode utilise plusieurs stratégies:

• Une stratégie comportementale pour sélectionner les actions (typiquement une stratégie de type ɛ-greedy pour continuer à explorer l'environnement)
• Une stratégie cible pour mettre à jour les valeurs d'actions.

La stratégie cible utilisée pour mettre à jour les valeurs d'actions est implicitement construite à travers l'opération max qui est utilisée dans l'équation de récurrence. On pourrait effectivement extraire cette opération en introduisant une stratégie cible qui sélectionnerait les actions de manière optimale par rapport aux valeurs d'actions courantes.

Ce qui est également confus avec l'algorithme Q-learning est qu'il ne fait pas intervenir de ratio d'échantillonnage préférentiel. Cela vient du fait que les mises à jours sont réalisées sur un unique pas de calcul. La définition de $Q(s,a)$ conditionne le premier pas à toujours prendre l'action $a$, et cela quelle que soit la probabilité de transition assignée à cette action par la stratégie comportementale (stratégie d'exploration). Dans ce cas, le ratio d'échantillonnage préférentiel ne joue aucun rôle ici.